﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace my_test
{
    class Program
    {
        static void Main(string[] args)
        {

            string[] str = new Solution().Permutation("abc");

            for (int i = 0; i < str.Length; i++)
            {
                Debug.WriteLine(str[i]);
            }
        }

        class Solution
        {
            //下一个排序法 解决字符串枚举问题
            public string[] Permutation(string s)
            {
                char[] strs = s.ToCharArray();
                Array.Sort(strs);
                List<string> ret = new List<string>();
                ret.Add(new string(strs));
                while (NextString(strs) == true)
                {
                    ret.Add(new string(strs));//第一个坑 直接存strs的话是个引用。后面更改值会让数组中所有值都被更改
                }

                string[] ret_arr = new string[ret.Count];
                for (int i = 0; i < ret.Count; i++)
                {
                    ret_arr[i] = ret[i].ToString();
                }

                return ret_arr;
            }
            public bool NextString(char[] strs)
            {
                int i = strs.Length - 2;
                int j = strs.Length - 1;
                int k = strs.Length - 1;
                if (i < 0)
                {
                    return false;
                }
                //找到相邻的升序对
                while (i >= 0 && strs[i] >= strs[j])
                {
                    i--;
                    j--;
                }
                if (i < 0)
                {
                    return false;
                }
                //从尾部开始寻找大于 a[i]的第一个数字                     
                while (k >= i && strs[i] >= strs[k])
                {
                    k--;
                }
                char temp = strs[i];
                strs[i] = strs[k];
                strs[k] = temp;
                for (int p = j; p < strs.Length-1; p++)
                {
                    for (int q = p+1; q < strs.Length; q++)
                    {
                        if (strs[p] > strs[q])
                        {
                            char temp_2 = strs[p];
                            strs[p] = strs[q];
                            strs[q] = temp_2;
                        }
                    }
                }
                return true;
            }
        }

    }


}
